import java.util.Arrays;

public class WU_96 {
    public static void main(String[] args) {
        double [] array={2,5,4,3,6,7,5,56};
        new WU_96().mergesort(array);
        System.out.println(Arrays.toString(array));
    }
    void mergesort(double [] array){
        int length =array.length;
        //返回条件
        if(length<=1) return;
        //分解数组
        int leftlength=length/2;
        int rightlength=length-leftlength;
        double [] leftarray=new double[leftlength];
        double [] rightarray=new double[rightlength];
        int j=0;
        for(int i=0;i<length;i++){
            if(i<leftlength){
                leftarray[i]=array[i];
            }
            else{
                rightarray[j++]=array[i];
            }
        }
        //递归分解
        mergesort(leftarray);
        mergesort(rightarray);
        //有序合并
        merge(leftarray,rightarray,array);

    }
    void merge(double [] leftarray ,double [] rightarray ,double [] array ){
        int leftSize= leftarray.length;
        int rightSize= rightarray.length;
        int i=0,l=0,r=0;
        while(l < leftSize && r < rightSize){
            if(leftarray[l]<rightarray[r]){
                array[i]=leftarray[l];
                l++;
                i++;
            }
            else {
                array[i]=rightarray[r];
                r++;
                i++;
            }
        }
        //处理多余元素
        //触发条件是l=leftSize,或者r=rightSize
        while(l<leftSize){
            array[i]=leftarray[l];
            i++;l++;
        }
        while(r<rightSize){
            array[i]=rightarray[r];
            i++;r++;
        }

    }
}
